#include "StdAfx.h"
#include "K3M_Algorithm.h"

int K3M_Algorithm::N[3][3] =	{	{128,1,2},
									{64, 0, 4},
									{32, 16, 8}
								};

int K3M_Algorithm::A0[48] =	{	3, 6, 7, 12, 14, 15, 24,
								28, 30, 31, 48, 56, 60, 62,
								63, 96, 112, 120, 124, 126,	127,
								129, 131, 135, 143, 159, 191, 192,
								193, 195, 199, 207, 223, 224, 225,
								227, 231, 239, 240, 241, 243, 247,
								248, 249, 251, 252, 253, 254
							};

int K3M_Algorithm::A1[8] = {7, 14, 28, 56, 112, 131, 193, 224};

int K3M_Algorithm::A2[15] = {7, 14, 15, 28, 30, 56, 60, 112, 120, 131, 135, 193, 195, 224, 240};

int K3M_Algorithm::A3[24] = {7, 14, 15, 28, 30, 31, 56, 60, 62, 112, 120, 124, 131, 135, 143, 193, 195, 199, 224, 225, 227, 240, 241, 248};

int K3M_Algorithm::A4[32] = {7, 14, 15, 28, 30, 31, 56, 60, 62, 63, 112, 120, 124, 126, 131, 135, 143, 159, 193, 195, 199, 207, 224, 225, 227, 231, 240, 241, 243, 248, 249, 252};

int K3M_Algorithm::A5[36] = {7, 14, 15, 28, 30, 31, 56, 60, 62, 63, 112, 120, 124, 126, 131, 135, 143, 159, 191, 193, 195, 199, 207, 224, 225, 227, 231, 239, 240, 241, 243, 248, 249, 251, 252, 254};

int K3M_Algorithm::A1pix[48] = {3, 6, 7, 12, 14, 15, 24, 28, 30, 31, 48, 56, 60, 62, 63, 96, 112, 120, 124, 126, 127, 129, 131, 135, 143, 159, 191, 192, 193, 195, 199, 207, 223, 224, 225, 227, 231, 239, 240, 241, 243, 247, 248, 249, 251, 252, 253, 254};

K3M_Algorithm::K3M_Algorithm(void)
{

}

void K3M_Algorithm::run(IplImage *source)
{
	bool isModified = false;
	do
	{
		isModified = false;

		this->marking_borders(source);
		isModified = (this->phase1(source) || isModified);
		isModified = (this->phase2(source) || isModified);
		isModified = (this->phase3(source) || isModified);
		isModified = (this->phase4(source) || isModified);
		isModified = (this->phase5(source) || isModified);
		this->borders.clear();
		
	}
	while (isModified);
	this->thinning_to_one_pixel_skeleton(source);
	return;	
}

void K3M_Algorithm::marking_borders(IplImage *source)
{
	this->borders.clear();

	for (int y = 0; y < source->height; y++)
	{
		for (int x = 0; x < source->width; x++)
		{
			// Calculate neighbourhood weight
			if (((uchar *)(source->imageData + y * source->widthStep))[x] == 0)
			{
				int neighbourhood_weight = 0;
				for (int k = -1; k < 2; k++)
				{
					for (int l = -1; l < 2; l++)
					{
						if ((y + k < 0) || (x + l < 0) || (y + k >= source->height) || (x + l >= source->width) )
						{
							neighbourhood_weight+= 0;
						}
						else
						{
							uchar pixel_value = (((uchar *)(source->imageData + (y + k) * source->widthStep))[x + l] == 255) ? 0 : 1;
							neighbourhood_weight+= K3M_Algorithm::N[k+1][l+1] * pixel_value;
						}
					}
				}

			
				if (binary_search(K3M_Algorithm::A0, K3M_Algorithm::A0 + 48, neighbourhood_weight))
				{
					this->borders.push_back(make_pair(y,x));
				}
			}
			
		}
	}
	return;
};

bool K3M_Algorithm::phase1(IplImage *source)
{
	bool isModified = false;
	for (int i = 0; i < (int) this->borders.size(); i++)
	{
		int x = this->borders[i].second;
		int y = this->borders[i].first;

			// Calculate neighbourhood weight

			int neighbourhood_weight = 0;
			for (int k = -1; k < 2; k++)
			{
				for (int l = -1; l < 2; l++)
				{
					if ((y + k < 0) || (x + l < 0) || (y + k >= source->height) || (x + l >= source->width) )
					{
						neighbourhood_weight+= 0;
					}
					else
					{
						uchar pixel_value = (((uchar *)(source->imageData + (y + k) * source->widthStep))[x + l] == 255) ? 0 : 1;
						neighbourhood_weight+= K3M_Algorithm::N[k+1][l+1] * pixel_value;
					}
				}
			}

			// Is the weight present in lookup array A1?
			if (binary_search(K3M_Algorithm::A1, K3M_Algorithm::A1 + 8, neighbourhood_weight))
			{
				((uchar *)(source->imageData + y * source->widthStep))[x] = 255;
				isModified = true;
			}
	}
	return isModified;
}

bool K3M_Algorithm::phase2(IplImage *source)
{
	bool isModified = false;
	for (int i = 0; i < (int) this->borders.size(); i++)
	{
		int x = this->borders[i].second;
		int y = this->borders[i].first;

			// Calculate neighbourhood weight

			int neighbourhood_weight = 0;
			for (int k = -1; k < 2; k++)
			{
				for (int l = -1; l < 2; l++)
				{
					if ((y + k < 0) || (x + l < 0) || (y + k >= source->height) || (x + l >= source->width) )
					{
						neighbourhood_weight+= 0;
					}
					else
					{
						uchar pixel_value = (((uchar *)(source->imageData + (y + k) * source->widthStep))[x + l] == 255) ? 0 : 1;
						neighbourhood_weight+= K3M_Algorithm::N[k+1][l+1] * pixel_value;
					}
				}
			}

			// Is the weight present in lookup array A2?
			if (binary_search(K3M_Algorithm::A2, K3M_Algorithm::A2 + 15, neighbourhood_weight))
			{
				((uchar *)(source->imageData + y * source->widthStep))[x] = 255;
				isModified = true;
			}
	}
	return isModified;
}

bool K3M_Algorithm::phase3(IplImage *source)
{
	bool isModified = false;
	for (int i = 0; i < (int) this->borders.size(); i++)
	{
		int x = this->borders[i].second;
		int y = this->borders[i].first;

			// Calculate neighbourhood weight

			int neighbourhood_weight = 0;
			for (int k = -1; k < 2; k++)
			{
				for (int l = -1; l < 2; l++)
				{
					if ((y + k < 0) || (x + l < 0) || (y + k >= source->height) || (x + l >= source->width) )
					{
						neighbourhood_weight+= 0;
					}
					else
					{
						uchar pixel_value = (((uchar *)(source->imageData + (y + k) * source->widthStep))[x + l] == 255) ? 0 : 1;
						neighbourhood_weight+= K3M_Algorithm::N[k+1][l+1] * pixel_value;
					}
				}
			}

			// Is the weight present in lookup array A3?
			if (binary_search(K3M_Algorithm::A3, K3M_Algorithm::A3 + 24, neighbourhood_weight))
			{
				((uchar *)(source->imageData + y * source->widthStep))[x] = 255;
				isModified = true;
			}
	}
	return isModified;
}

bool K3M_Algorithm::phase4(IplImage *source)
{
	bool isModified = false;
	for (int i = 0; i < (int) this->borders.size(); i++)
	{
		int x = this->borders[i].second;
		int y = this->borders[i].first;

			// Calculate neighbourhood weight

			int neighbourhood_weight = 0;
			for (int k = -1; k < 2; k++)
			{
				for (int l = -1; l < 2; l++)
				{
					if ((y + k < 0) || (x + l < 0) || (y + k >= source->height) || (x + l >= source->width) )
					{
						neighbourhood_weight+= 0;
					}
					else
					{
						uchar pixel_value = (((uchar *)(source->imageData + (y + k) * source->widthStep))[x + l] == 255) ? 0 : 1;
						neighbourhood_weight+= K3M_Algorithm::N[k+1][l+1] * pixel_value;
					}
				}
			}

			// Is the weight present in lookup array A4?
			if (binary_search(A4, A4 + 32, neighbourhood_weight))
			{
				((uchar *)(source->imageData + y * source->widthStep))[x] = 255;
				isModified = true;
			}
	}
	return isModified;
}

bool K3M_Algorithm::phase5(IplImage *source)
{
	bool isModified = false;
	for (int i = 0; i < (int) this->borders.size(); i++)
	{
		int x = this->borders[i].second;
		int y = this->borders[i].first;

			// Calculate neighbourhood weight

			int neighbourhood_weight = 0;
			for (int k = -1; k < 2; k++)
			{
				for (int l = -1; l < 2; l++)
				{
					if ((y + k < 0) || (x + l < 0) || (y + k >= source->height) || (x + l >= source->width) )
					{
						neighbourhood_weight+= 0;
					}
					else
					{
						uchar pixel_value = (((uchar *)(source->imageData + (y + k) * source->widthStep))[x + l] == 255) ? 0 : 1;
						neighbourhood_weight+= K3M_Algorithm::N[k+1][l+1] * pixel_value;
					}
				}
			}

			// Is the weight present in lookup array A5?
			if (binary_search(K3M_Algorithm::A5, K3M_Algorithm::A5 + 36, neighbourhood_weight))
			{
				((uchar *)(source->imageData + y * source->widthStep))[x] = 255;
				isModified = true;
			}
	}
	return isModified;
}

void K3M_Algorithm::thinning_to_one_pixel_skeleton(IplImage *source)
{

	for (int y = 0; y < source->height; y++)
	{
		for (int x = 0; x < source->width; x++)
		{
			// Calculate neighbourhood weight
			if (((uchar *)(source->imageData + y * source->widthStep))[x] == 0)
			{
				int neighbourhood_weight = 0;
				for (int k = -1; k < 2; k++)
				{
					for (int l = -1; l < 2; l++)
					{
						if ((y + k < 0) || (x + l < 0) || (y + k >= source->height) || (x + l >= source->width) )
						{
							neighbourhood_weight+= 0;
						}
						else
						{
							uchar pixel_value = (((uchar *)(source->imageData + (y + k) * source->widthStep))[x + l] == 255) ? 0 : 1;
							neighbourhood_weight+= K3M_Algorithm::N[k+1][l+1] * pixel_value;
						}
					}
				}

			
				if (binary_search(K3M_Algorithm::A1pix, K3M_Algorithm::A1pix + 48, neighbourhood_weight))
				{
					((uchar *)(source->imageData + y * source->widthStep))[x] = 255;
				}
			}
			
		}
	}
	return;
}

K3M_Algorithm::~K3M_Algorithm(void)
{
}
